package com.ljy.my_study.leetcode.字符串的排列;

import java.util.Arrays;
import java.util.LinkedHashSet;
import java.util.Set;

public class TestMain {

//    输入一个字符串，打印出该字符串中字符的所有排列。
//
//             
//
//    你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。
//
//             
//
//    示例:
//
//    输入：s = "abc"
//    输出：["abc","acb","bac","bca","cab","cba"]
//             
//
//    限制：
//
//            1 <= s 的长度 <= 8
//
//    来源：力扣（LeetCode）
//    链接：https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof
//    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

    public String[] permutation(String s) {
        char[] chars=s.toCharArray();
        Arrays.sort(chars);
        int len=chars.length;
        Set<String> set=new LinkedHashSet<>();
        dfs(chars,new boolean[len],new char[len],0,set);
        String[] result=new String[set.size()];
        int i=0;
        for(String e:set){
            result[i++]=e;
        }
        return result;
    }

    private void dfs(char[] chars,boolean[] visited,char[] array,int index,Set<String> set){
        int len=chars.length;
        if(index==len){
            set.add(String.valueOf(array));
        }
        for(int i=0;i<len;i++){
            if(visited[i]){
                continue;
            }
            array[index]=chars[i];
            visited[i]=true;
            dfs(chars,visited,array,index+1,set);
            visited[i]=false;
            array[index]='a';
        }
    }
}
